package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Problem092 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int c = 0;
		for (int i = 1; i < 10000000; i ++) {
			if (end(i)) {
				c ++;
			}
		}
		System.out.println(c);
	}
	static Map<Long, Boolean> map = new HashMap<Long, Boolean>();
	
	public static boolean end(long n) {
		long k = n;
		List<Long> list = new ArrayList<Long>();
		while (true) {
			if (k == 1) {
				return false;
			} else if (k == 89) {
				for (Long l: list) {
					map.put(l, true);
				}
				return true;
			} else {
				if (map.get(k) != null) {
					return true;
				} else {
					list.add(k);
					k = next(k);
				}
			}
		}
	}
	
	public static long next(long n) {
		long m = n;
		long t = 0;
		while (m > 0) {
			long a = m%10;
			t += a*a;
			m /= 10; 
		}
		return t;
	}
}
